package com.itheima.leetcode.od.b.violentenumeration;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;

/**
 * (A卷,200分)- 无向图染色（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 给一个无向图染色，可以填红黑两种颜色，必须保证相邻两个节点不能同时为红色，输出有多少种不同的染色方案？
 * <p>
 * 输入描述
 * <p>
 * 第一行输入M(图中节点数) N(边数)
 * <p>
 * 后续N行格式为：V1 V2表示一个V1到V2的边。
 * <p>
 * 数据范围：1 <= M <= 15,0 <= N <= M * 3，不能保证所有节点都是连通的。
 * <p>
 * 输出描述
 * <p>
 * 输出一个数字表示染色方案的个数。
 * <p>
 * 用例
 * <p>
 * 输入	4 4
 * <p>
 * 1 2
 * <p>
 * 2 4
 * <p>
 * 3 4
 * <p>
 * 1 3
 * <p>
 * 输出	7
 * 说明
 * 4个节点，4条边，1号节点和2号节点相连，
 * <p>
 * 2号节点和4号节点相连，3号节点和4号节点相连，
 * <p>
 * 1号节点和3号节点相连，
 * <p>
 * 若想必须保证相邻两个节点不能同时为红色，总共7种方案。
 * <p>
 * 输入	3 3
 * <p>
 * 1 2
 * <p>
 * 1 3
 * <p>
 * 2 3
 * <p>
 * 输出	4
 * 说明	无
 * <p>
 * 输入	4 3
 * <p>
 * 1 2
 * <p>
 * 2 3
 * <p>
 * 3 4
 * <p>
 * 输出	8
 * 说明	无
 * <p>
 * 输入	4 3
 * <p>
 * 1 2
 * <p>
 * 1 3
 * <p>
 * 2 3
 * <p>
 * 输出	8
 * 说明	无
 * <p>
 * 题目解析
 * <p>
 * 2022.12.25 更正解析说明，感谢Andy___Zhong指出错误。
 * <p>
 * 本题其实就是求解连通图的染色方案，
 * <p>
 * 目前我想到的最好方式是暴力法，即通过回溯算法，求解出染红节点的全组合，
 * <p>
 * n个数的全组合数量一共有 (2^n) - 1。
 * <p>
 * 比如：1,2,3的全组合情况有：1、2、3、12、13、23、123，即 (2^3) - 1 = 7个。
 * <p>
 * 本题中节点一共有m个，而1 <= m <= 15，即最多有 (2^15) - 1 = 32767 个组合情况，这个数量级不算多。 因此暴力法可行。
 * <p>
 * 我们需要尝试对组合中的节点进行染红色，但是相邻节点不能同时染成红色。因此，在求解全组合时，还可以进行剪枝优化，即判断新加入的节点  是否和 已存在的节点相邻，如果相邻，则剪枝，如果不相邻则继续递归。
 */
public class UndirectedGraphStaining {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();
        int n = sc.nextInt();

        int[][] edges = new int[n][2];
        for (int i = 0; i < n; i++) {
            edges[i][0] = sc.nextInt();
            edges[i][1] = sc.nextInt();
        }*/

        String input = "1 2\n2 4\n3 4\n1 3";
        int[][] edges = Arrays.stream(input.split("\n"))
                .map(s -> Arrays.stream(s.split(" "))
                        .mapToInt(Integer::parseInt)
                        .toArray())
                .toArray(int[][]::new);

        System.out.println(getResult(edges, 4));
        System.out.println(getResult2(edges, 4));
    }

    /**
     * 图的组合回溯
     *
     * @param edges 边，即[v1, v2]
     * @param m     点数量
     * @return
     */
    public static int getResult(int[][] edges, int m) {
        // connect用于存放每个节点的相邻节点
        HashMap<Integer, HashSet<Integer>> connect = new HashMap<>();

        for (int[] edge : edges) {
            connect.putIfAbsent(edge[0], new HashSet<>());
            connect.get(edge[0]).add(edge[1]);

            connect.putIfAbsent(edge[1], new HashSet<>());
            connect.get(edge[1]).add(edge[0]);
        }

        // 节点从index=1开始，必有count=1个的全黑染色方案
        return dfs(connect, m, 1, 1, new LinkedList<>());
    }

    /**
     * 该方法用于求解给定多个节点染红的全组合数
     *
     * @param connect
     * @param m
     * @param index
     * @param count
     * @param path
     * @return
     */
    public static int dfs(
            HashMap<Integer, HashSet<Integer>> connect,
            int m,
            int index,
            int count,
            LinkedList<HashSet<Integer>> path) {
        if (path.size() == m) {
            return count;
        }

        outer:
        for (int i = index; i <= m; i++) {
            // 如果新加入节点i和已有节点j相邻，则说明新加入节点不能染成红色，需要进行剪枝
            for (HashSet<Integer> p : path) {
                if (p.contains(i)) {
                    continue outer;
                }
            }

            count++;

            if (connect.containsKey(i)) {
                path.addLast(connect.get(i));
                count = dfs(connect, m, i + 1, count, path);
                path.removeLast();
            } else {
                count = dfs(connect, m, i + 1, count, path);
            }
        }

        return count;
    }

    /**
     * 状态压缩 + 暴力枚举
     *
     * @param edges
     * @param m
     * @return
     */
    public static int getResult2(int[][] edges, int m) {
        int count = 0;
        //遍历所有可能的组合 举例： 10001 -> i 的二进制表达
        for (int i = 0; i < (1 << m); i++) {
            boolean flag = true;
            for (int j = 0; j < edges.length; j++) {
                // 检测所有的边相连的是否同为红颜色
                /*if (((i >> (m - edgeArrayList.get(j).get(0))) & 1) == 1
                        && ((i >> (m - edgeArrayList.get(j).get(1))) & 1) == 1) { // 从左往右排
                    flag = false;
                    break;
                }*/
                if (((i >> (edges[j][0] - 1)) & 1) == 1
                        && ((i >> (edges[j][1] - 1)) & 1) == 1) { // 建议用这个，从右往左排
                    flag = false;
                    break;
                }
            }
            if (flag) {
                count++;
            }
        }
        return count;
    }
}